#include <iostream>
#include <cstdio>
#include <queue>
#include <cstring>
using namespace std;
const int MAXN=1e6+7;
int res[MAXN];
int res2[MAXN];
int x[]={2,3,5,7,11,13};
void SPFA1() {
    memset(res, 0x3f, sizeof(res));
    queue<int> q;
    res[1]=0;
    q.push(1);
    while (!q.empty()) {
        int now=q.front();
        q.pop();
        for (int i=0; i<6; i++) {
            if (now*x[i]<MAXN-1 && res[now*x[i]] > res[now] + x[i]) {
                res[now*x[i]] = res[now] + x[i];
                q.push(now*x[i]);
            }
        }
        if (now > 1 && res[now-1] > res[now] + 1) {
            res[now-1] = res[now] + 1;
            q.push(now-1);
        }
    }
}
void SPFA2() {
    memset(res2, 0x3f, sizeof(res2));
    queue<int> q;
    res2[1]=0;
    q.push(1);
    while (!q.empty()) {
        int now=q.front();
        q.pop();
        for (int i=0; i<5; i++) {
            if (now*x[i]<MAXN-1 && res2[now*x[i]] > res2[now] + x[i]) {
                res2[now*x[i]] = res2[now] + x[i];
                q.push(now*x[i]);
            }
        }
        if (now > 1 && res2[now-1] > res2[now] + 1) {
            res2[now-1] = res2[now] + 1;
            q.push(now-1);
        }
    }
}
int main() {
    int n;
    SPFA1();
    SPFA2();
    for (int i=0; i<MAXN; ++i) {
    	if (res[i]!=res2[i]) cout<<i<<' '<<res[i]<<' '<<res2[i]<<endl;
	}
    cin>>n;
    printf("%d\n", res[n]);
    return 0;
}
